There is great interest in the development of computer systems which enable users to generate quickly accurate displays and reproductions of real world objects, terrains and other 3D surfaces. A graphic display and manipulation system generates a mesh model of the object, terrain or surface, uses that mesh model as a basis to create the display or reproduction and allows the user to manipulate the model to create other displays such as "morphs," fantasy displays or special effects. A mesh model represents an object, terrain or other surface as a series of interconnected planar shapes, such as sets of triangles, quadrangles or more complex polygons. More advanced graphic display systems provide rapid zoom and "walk around" capabilities (allowing the viewer to make his or her perceived vantage point appear to move closer to, farther from or about an object or surface). These systems must have the ability to quickly generate a mesh of high quality for reproduction of the object.
A set of data points that describes the object or surface provides basic data for the mesh. The data points represent actual, measured points on the object, surface or terrain. Their values come from a number of sources. A user can input data points based on measurement or planned architecture or they can be generated through scanning and other measuring systems. A scanning system uses a light source such as a laser stripe to scan and a camera to collect images of the scanning light as it reflects from the object. A scanning system processes the information captured in the images to determine a set of measured 3D point values that describe the object, surface or terrain in question. Scanning systems can easily gather the raw data of several hundred thousand 3D coordinates. The data points come to the mesh modeling system as a group of randomly distributed points. Other data concerning the object, terrain or surface, such as a texture map, ambient light data or color or luminosity information, can be associated or used in conjunction with the geometric shapes of the mesh.
Typical mesh modeling systems use data points either indirectly (in gridded network models) or directly (in irregular network models) to create meshes. U.S. Pat. No. 4,888,713 to Falk and U.S. Pat. No. 5,257,346 to Hanson describe ways of creating gridded mesh representations. Gridded network models superimpose a grid structure as the basic framework for the model surface. The grid point vertices form the interconnected geometric faces which model the surface. The computer connects the grid points to form evenly distributed, geometric shapes such as triangles or squares, that fit within the overall grid structure. While gridded models provide regular, predictable structures, they are not well suited for mesh construction based on an irregular, random set of data points, such as those generated through laser scanning (as mentioned above). To fit the irregular data points of a laser scan into a rigid grid structure, the data point values must be interpolated to approximate points at the grid point locations. The need to interpolate increases computation time and decreases the overall accuracy of the model.
Compared to a gridded model, an irregular mesh model provides a better framework for using irregular data points, because the irregularly-spaced data points themselves can be used as the vertices in the framework, without the need to interpolate their values to preset grid point locations. A typical irregular network meshing system builds a mesh by constructing edge lines between data points to create the set of geometric faces that approximate the surface of the object or terrain. There has been widespread interest in building irregular mesh models having planar faces of triangular shapes, as only three points are needed to determine a planar face.
While irregular triangular meshes offer the possibility of more accurate displays, the systems to implement them are more complex compared to gridded network models. The limitations of the computer hardware and the complexity inherent in the data structures needed for implementation of irregular mesh building systems has prevented their widespread use. U.S. Pat. No. 5,440,674 to Park and U.S. Pat. No. 5,214,752 to Meshkat et al. describe meshing systems used for finite element analysis, i.e., the partitioning of CAD diagrams into a series of mesh faces for structural analysis, not the creation of a mesh from a series of raw data points. As such, the systems do not appear suitable for the rapid mesh generation requirements of applications such as computer animation and special effects and they do not appear suitable for creating meshes from a large number of sampled data points.
For computer mesh applications involving the hundreds of thousands of 3D data points typically used in computer graphics and animation and graphic display systems, there is a need for the creation of a mesh system which can generate a mesh with substantial speed. Speed and data storage requirements are also important factors in graphic display applications on communication systems such as the Internet. Currently, Internet graphic displays are typically communicated as massive 2D pixel streams. Each and every pixel displayed in a 2D image must have a pixel assignment. All of those pixel assignments must be transmitted via the communications system. Such a transmission requires large amounts of communication time. Further, if movement is depicted in the display, information must be continuously sent over the communications system to refresh the image or, in the alternative, one large chunk of pixel data must be downloaded to the receiving terminal before the display can begin. Replacing the 2D image display system with a 3D modeling system substantially reduces the amount of data needed to be transmitted across the communication system, because with a 3D modeling system only representative 3D data points need be sent--not a full set of assignments for every pixel displayed. A mesh generating system located at the receiver terminal could generate a full display of the object upon receiving relatively few 3D data points. Currently available meshing systems do not provide this capability.
The demands of computer animation and graphic display also call for improvement in the quality of the mesh. In the case of an irregular triangulated mesh, for example, when the angles of one triangle's corners vary widely from the angles of another triangle or the triangles differ wildly in shape and size, the mesh tends to be difficult to process for functions such as "gluing" (joining a mesh describing one part of an object to a mesh describing an adjacent part). Such a mesh will also display badly. For example, a non-optimized triangulated mesh might show a jagged appearance in the display of what are supposed to be smooth curving surfaces like the sides of a person's face. Generally, an underlying mesh model constructed from small, regularly angled triangles that tend towards being equilateral is preferable.
The procedure of B. Delaunay known as "Delaunay Triangulation" is one optimization theory which researchers have attempted to implement for the construction of a high quality, irregular meshes with homogeneous triangular structure. Delaunay's theories for the creation of irregular mesh lattices derive from the teachings of M. G. Voronoi and the studies he made of "Voronoi polygons". Voronoi determined that, for a set of data points in space, a proximity region could be defined for each data point by a convex polygon created from the perpendicular bisectors of lines drawn from the point in question to its nearest neighbors. FIG. 1a shows an example of a Voronoi polygon. Each data point is bounded by a unique Voronoi polygon created through those bisecting lines. The edges of each Voronoi polygon are shared with Voronoi polygons for the interconnected points. Thus, Voronoi's method describes a surface with a series of unique, complex polygons. FIG. 1b depicts an example of a Voronoi polygon diagram.
Delaunay's theories follow the teachings of Voronoi and seek to create an irregular triangulated mesh with a tendency for homogeneous triangles. It has been proven that every vertex of a Voronoi diagram is the common intersection of exactly three polygonal edges. Equivalently, it has been proven that each vertex of a Voronoi polygon is a center of a circle defined by three of the data points bounded by the Voronoi polygons. See, e.g., Computational Geometry, Preparata and Shamos, New York, Springes-Verlag, 1988 (second printing). From those observations, it is possible to create from any Voronoi diagram a "straight-line dual" diagram having similar properties. FIG. 1c depicts a straight line dual diagram made from the data points bounded by the Voronoi polygon in FIG. 1b. Notice that the "straight-line dual" is a triangular mesh constructed using the actual data points, not the vertices of the Voronoi polygons created by the bisecting lines. The straight-line dual diagram forms its triangular mesh shape by constructing straight line segments between each pair of data points whose Voronoi polygons share an edge. (See FIG. 1c.) It has been proven that a straight line dual of a Voronoi diagram always produces an irregular triangulated mesh. Ibid.
Delaunay used the Voronoi straight line dual to create triangulated lattices with properties derived from an understanding of the Voronoi polygonal diagram. When a triangulation follows Delaunay principles, a circumcircle defined by the vertices of a triangle will not contain another data point of the mesh. FIG. 1d depicts a circumcircle for determination of whether the triangle meets the Delaunay optimality criteria. A Delaunay mesh procedure guarantees that for each triangle of the mesh the area within a circumcircle created from the three vertices will not contain any other data point of the mesh.
Research shows that a triangulated mesh which adheres to the Delaunay circumcircle principle yields an optimied mesh which behaves well in display and graphic manipulations systems. However, Delaunayian meshing procedures, such as those described by Park and Meshkat, for example, do not operate at high speed to build a mesh from a large set of raw data points. The few currently available meshing procedures which even attempt to optimize Delaunay theories use slow recursive means that rely on time-consuming parameter passing and checking steps. Such problems have stifled the use of real-life object depictions in computer graphics applications.
Therefore, it would represent a substantial advance in the field if a computer modeling system could be developed that allows for rapid generation of a mesh optimized by principles such as those set forth in the theories of Delaunay and Voronoi. Such a system would enable computer graphics systems to use real world images in all applications. The system would enable communication systems, such as the Internet, to display and manipulate images and models of the real world objects more rapidly.